package main.leetcode.clockin.March;

/**
 * 1162.地图分析
 *
 * <p>你现在手里有一份大小为 N x N
 * 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
 *
 * <p>我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
 *
 * <p>如果我们的地图上只有陆地或者海洋，请返回 -1。
 *
 * <p>
 *
 * <p>示例 1：输入：[[1,0,1],[0,0,0],[1,0,1]] 输出：2 解释： 海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
 *
 * <p>示例 2：输入：[[1,0,0],[0,0,0],[0,0,0]] 输出：4 解释： 海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。
 *
 * <p>提示：1 <= grid.length == grid[0].length <= 100 grid[i][j] 不是 0 就是 1
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day29 {
    public static void main(String[] args) {
        // int[][] grid = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
        int[][] grid = {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}};
        System.out.println(new day29().maxDistance(grid));
    }

    // 多源bfs
    //    public int maxDistance(int[][] grid) {
    //        int n = grid.length;
    //        if (n == 0) return -1;
    //        int[][] tmp = grid.clone();
    //        Queue<Integer> land = new LinkedList<>();
    //        for (int i = 0; i < n; i++) {
    //            for (int j = 0; j < n; j++) {
    //                if (tmp[i][j] == 1) land.add(i * n + j);
    //            }
    //        }
    //        int curSize = land.size();
    //        if (curSize == 0 || curSize == n * n) return -1;
    //        int[][] directions = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    //        int curX, curY, newX, newY;
    //        int root;
    //        int res = 0;
    //        while (!land.isEmpty()) {
    //            curSize = land.size();
    //            for (int i = 0; i < curSize; i++) {
    //                root = land.poll();
    //                curX = root / n;
    //                curY = root % n;
    //                for (int[] dir : directions) {
    //                    newX = curX + dir[0];
    //                    newY = curY + dir[1];
    //                    if (newX >= 0 && newX < n && newY >= 0 && newY < n && tmp[newX][newY] ==
    // 0) {
    //                        tmp[newX][newY] = 1;
    //                        land.add(newX * n + newY);
    //                    }
    //                }
    //            }
    //            ++res;
    //        }
    //        return res - 1;
    //    }

    // 动态规划
    // 对于每个海洋区域 (x, y)(x,y)，离它最近的陆地区域到它的路径要么从上方或者左方来，要么从右方或者下方来
    // 第一次从左上到右下 f(x,y)=min(f(x-1,y),f(x,y-1))+1 for land or 0 for ocean
    // 第二次从右下到左上 f(x,y)=min(f(x+1,y),f(x,y+1))+1 for land or 0 for ocean
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        int[][] tmp = grid.clone();
        int i, j;

        // 从左上到右下
        for (i = 0; i < n; ++i) {
            for (j = 0; j < n; ++j) {
                if (tmp[i][j] != 1) {
                    tmp[i][j] = n * n;
                    if (i > 0) tmp[i][j] = Math.min(tmp[i][j], tmp[i - 1][j] + 1);
                    if (j > 0) tmp[i][j] = Math.min(tmp[i][j], tmp[i][j - 1] + 1);
                }
            }
        }

        int res = 0;
        // 从右下到左上
        for (i = n - 1; i >= 0; --i) {
            for (j = n - 1; j >= 0; --j) {
                if (tmp[i][j] != 1) {
                    if (i < n - 1) tmp[i][j] = Math.min(tmp[i][j], tmp[i + 1][j] + 1);
                    if (j < n - 1) tmp[i][j] = Math.min(tmp[i][j], tmp[i][j + 1] + 1);
                    res = Math.max(res, tmp[i][j]);
                }
            }
        }
        return res == n * n ? -1 : res - 1;
    }
}
